/*
 * Copyright 2013 Kenneth Syharath
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the license at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the license is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the license for specific language governing
 * permissions and limitations under the license.
 */

package shuffler_classes;

import java.util.Deque;
import java.util.List;
import java.util.Random;

import com.google.common.collect.Lists;
import com.google.common.collect.Queues;


/** 
 * Shufflers.java
 * @author  Kenneth Syharath
 * @version 1.0
 * All functions strip type from lists. It is highly recommended that all 
 * users cast all lists returned by this library back to their original types.
 */
public class Shufflers {
	
	/**
	 * This function is the Fisher-Yates Shuffle.
	 * The Fisher-Yates is a guaranteed fully random shuffling
	 * algorithm, also known as the Knuth-Yates algorithm.
	 * The algorithm is equivalent to starting at the top of the deck,
	 * looking at the current card, rolling a die with sides equal to
	 * the number of cards below that position, and switching the current
	 * card and the result.
	 * @param inList	The array to be shuffled.
	 * @return			The shuffled array.
	 */
	public static List fisherYatesShuffle(List inList) {
		
		if (inList == null)
			throw new IllegalArgumentException("Invalid array: " +
					"array argument is null");
		else if (inList.isEmpty())
			throw new IllegalArgumentException("Invalid array: " +
					"cannot shuffle an empty array");
		List retList = Lists.newArrayList();
		Random seedGen = new Random(System.nanoTime());
		
		while (!inList.isEmpty()) {
			Random ranGen = new Random(seedGen.nextLong());
			int elementID = ranGen.nextInt(inList.size());
			retList.add(inList.get(elementID));
			inList.remove(elementID);
		}
		
		return retList;
	}
	
	/**
	 * This function shuffles the given array by simulating a human 
	 * strip shuffle. The shuffle strips from the right of the given array;
	 * this is taken to mean the "bottom" of the provided "deck".
	 * @param inList			The array to be shuffled.
	 * @param windowSize		The proportion of the deck committed to
	 * 								generating the strip. This is varied by a 
	 * 								derived factor of the windowVariation.
	 * @param windowVariation	The factor that controls the random 
	 * 								variation in the windowSize. The windowSize
	 * 								varies by multiplying by a derived factor 
	 * 								of this value.
	 * @param numCascades		The number of times to cascade the shuffle.
	 * 								For a strip shuffle, this cascades the 
	 * 								shuffle on the strip itself instead of 
	 * 								repeating the shuffle multiple times.
	 * @return 					A shuffled version of the original array, 
	 * 								returned as a generic list.
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static List stripShuffle(List inList, double windowSize,
			double windowVariation, int numCascades) {
		if (inList.isEmpty())
			throw new IllegalArgumentException("Invalid array: " +
					"Cannot shuffle an empty array");
		else if (windowSize > 1 || windowSize < -1)
			throw new IllegalArgumentException("Invalid window size: Window " 
					+ "size must be a double between 0.00 and 1.00");
		else if ((windowVariation * windowSize) > 1.00)
			throw new IllegalArgumentException("Invalid variation: window " 
					+ "size * window variation cannot represent a larger " +
					"proportion of the array than exists");
		else if (numCascades < 0)
			throw new IllegalArgumentException("Invalid number of cascades: " +
					"Cascade count cannot be negative.");
		Deque theDeck = Queues.newArrayDeque(inList);
		Deque theStrip = Queues.newArrayDeque();
		double variation = new Random(System.nanoTime()).nextDouble() * windowVariation;
		int stripSize = (int) (theDeck.size() * variation);
		
		if (numCascades == 0) {
			for (int i = 0; i < stripSize; i++)
				theDeck.offerFirst(theDeck.pollLast());
			return Lists.newArrayList(theDeck);
		}
		else if (numCascades > stripSize)
			numCascades = stripSize;
		
		for (int i = 0; i < stripSize; i++)
			theStrip.offerFirst(theDeck.pollLast());
	
		for (int i = 0; i < numCascades; i++) {
			if (theStrip.isEmpty())
				break;
			Deque miniStrip = Queues.newArrayDeque();
			double miniStripVar = new 
					Random(System.nanoTime()).nextDouble() * windowVariation;
			int miniStripSize = (int) (theStrip.size() * miniStripVar);
			if (miniStripSize <= 0)
				miniStripSize = 1;
			for (int j = 0; j < miniStripSize; j++)
				miniStrip.offerLast(theStrip.pollFirst());
			while(!miniStrip.isEmpty())
				theDeck.offerFirst(miniStrip.pollLast());
		}
		
		while (!theStrip.isEmpty())
			theDeck.offerFirst(theStrip.pollLast());
		
		return Lists.newArrayList(theDeck);
	}
	
	/**
	 * This function shuffles the given array by simulating a human 
	 * riffle shuffle, more commonly known as a bridge or cascade shuffle.
	 * @param inList		The array to be shuffled.
	 * @param riffleWeight	The amount by which to favor one half or the other.
	 * @param favorTop		Whether or not to favor the "top" or left half.
	 * 							If false, assumes the bottom is favored.
	 * @return				A shuffled version of the original array, 
	 * 							returned as a generic list.
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static List riffleShuffle(List inList, int riffleWeight,
			boolean favorTop) {
		if (inList.isEmpty())
			throw new IllegalArgumentException("Cannot shuffle an empty " +
					"array");
		else if (riffleWeight <= 0)
			throw new IllegalArgumentException("Riffle weight must be " +
					"positive");
		
		int deckSize = inList.size();
		Deque theDeck = Queues.newArrayDeque(inList); 
		Deque topHalf = Queues.newArrayDeque();
		Deque botHalf = Queues.newArrayDeque();
		
		for (int i = 0; i < deckSize / 2; i++)
			botHalf.offerLast(theDeck.pollLast());
		topHalf.addAll(theDeck);
		theDeck.clear();
		
		while (!topHalf.isEmpty() || !botHalf.isEmpty()) {
			if (topHalf.isEmpty()) {
				theDeck.addAll(botHalf); 
				botHalf.clear();
				break;
			}
			if(botHalf.isEmpty()) {
				theDeck.addAll(topHalf); 
				topHalf.clear();
				break;
			}
			
			int ranNum = new Random(System.nanoTime()).nextInt(riffleWeight);
			
			if(favorTop) {
				if (ranNum % riffleWeight == 0)
					theDeck.offerFirst(botHalf.pollLast());
				else
					theDeck.offerFirst(topHalf.pollLast());	
			}
			else {
				if (ranNum % riffleWeight == 0)
					theDeck.offerFirst(topHalf.pollLast());
				else
					theDeck.offerFirst(botHalf.pollLast());	
			}
		}
		
		return Lists.newArrayList(theDeck);
	}
	
	/**
	 * This function shuffles the given array by simulating the 
	 * Mongean shuffle; this particular shuffle has an output of the following
	 * order: 2n, 2n-2, 2n-4, ..., 4, 2, 1, 3, 5, ..., 2n-5, 2n-3, 2n-1
	 * Note: 8 perfectly completed Mongean shuffles return the deck to its
	 * original configuration.
	 * @param inList	The array to be shuffled.
	 * @return			A shuffled version of the original array, 
	 * 						returned as a generic list.
	 */
	public static List mongeanShuffle(List inList) {
		Deque theStartDeck = Queues.newArrayDeque(inList);
		Deque theEndDeck = Queues.newArrayDeque();
		List retList;
		
		theEndDeck.offer(theStartDeck.poll());
		
		while (!theStartDeck.isEmpty()) {
			theEndDeck.offerFirst(theStartDeck.poll());
			
			if (theStartDeck.isEmpty())
				break;
			
			theEndDeck.offerLast(theStartDeck.poll());
		}
		
		retList = Lists.newArrayList(theEndDeck);
		
		return retList;
	}
	
	/**
	 * This function shuffles the given array by simulating a simplistic 
	 * human pile shuffle.
	 * @param inList			The array to be shuffled.
	 * @param numPiles			The number of piles to divide the deck into.
	 * @param numCascades		The number of times to cascade the shuffle.
	 * 								In this case, cascading the function means
	 * 								to deal from one of the piles to the
	 * 								remaining piles. The function does this
	 * 								ordinally and does not currently support
	 * 								random selection of the pile to cascade.
	 * @param randomizedStack	Whether or not to stack all existing piles in
	 * 								random order. If false, stacks the piles in
	 * 								the naive ordinal fashion.
	 * @return					A shuffled version of the original array,
	 * 								returned as a generic list.
	 */
	public static List pileShuffle(List inList, int numPiles,
			int numCascades, boolean randomizedStack) {
		
		if (numPiles > inList.size())
			throw new IllegalArgumentException("The number of piles is " +
					"greater than the size of the array.");
		else if (numCascades < 0)
			throw new IllegalArgumentException("The number of cascades " +
					"is negative.");
		else if (numCascades == 0) {
			Deque theDeck = Queues.newArrayDeque(inList);
			List<Deque> thePiles = Lists.newArrayListWithCapacity(numPiles);
			for (int i = 0; i < numPiles; i++)
				thePiles.add(Queues.newArrayDeque());
			return stackPilesIntoDeck(dealDeckIntoPiles(theDeck, thePiles),
					randomizedStack);
		}
		else {
			Deque theDeck = Queues.newArrayDeque(inList);
			List<Deque> thePiles = Lists.newArrayListWithCapacity(numPiles);
			for (int i = 0; i < numPiles; i++)
				thePiles.add(Queues.newArrayDeque());
			thePiles = dealDeckIntoPiles(theDeck, thePiles);
			
			for (int i = 0; i < numCascades; i++) {
				Deque curDeck = thePiles.get(0);
				thePiles.remove(0);
				thePiles = dealDeckIntoPiles(curDeck, thePiles);
			}
			
			return stackPilesIntoDeck(thePiles, randomizedStack);
		}
	}
	
	private static List<Deque> dealDeckIntoPiles(Deque theDeck, List<Deque> inPiles) {
		int curDequePos = 0;
		
		while (!theDeck.isEmpty()) {
			inPiles.get(curDequePos).offerFirst(theDeck.pollFirst());
			curDequePos = (curDequePos + 1) % inPiles.size();
		}
		
		return inPiles;
	}

	private static List stackPilesIntoDeck(List<Deque> inPiles,
			boolean randomized) {
		
		List retList = Lists.newArrayList();
		
		if (randomized) {
			Random ranGen = new Random(System.nanoTime());
			
			while (!inPiles.isEmpty()) {
				int ranNum = ranGen.nextInt(inPiles.size());
				Deque curDeck = inPiles.get(ranNum);
				for (Object obj : curDeck)
					retList.add(obj);
				inPiles.remove(ranNum);
			}
		}
		
		else
			for (Deque curPile : inPiles)
				retList.addAll(curPile);
		
		return retList;
	}
}
